package DynamicProgramming;
/**
 * P198 打家劫舍
 * */
public class P198 {


    public static void main(String[] args) {
//        int[] nums=new int[]{1,2,3,1};
        int[] nums=new int[]{2,7,9,3,1};
        P198Test01 p198Test01 = new P198Test01();
        System.out.println(p198Test01.rob(nums));
    }
}

class P198Test01{
    public int rob(int[] nums) {
        int length=nums.length;
        // 特判
        if(length==1){
            return nums[0];
        }
        if(length==2){
            return Math.max(nums[0],nums[1]);
        }
        // 初始化dp（最有数组）
        int[] dp=new int[length+1];
        // 将前两个判断出最优解
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        // 分步骤，每个步骤（子问题）去最优（最大/最小值问题）
        for(int i=2;i<length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[length-1];
    }
}
